package algorithm.leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class LeetCode_659_isPossible {
    /***
     * 使用map + 最大堆来实现
     * map -> key:num , value:priorityQueue
     * @param nums
     * @return
     */
    public boolean isPossible(int[] nums) {
        if (nums.length < 3) return false;
        Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        for (Integer num : nums) {
            if (!map.containsKey(num)) {
                map.put(num, new PriorityQueue<>());
            }
            //若包含当前数-1的数字 则将他的队长+1
            if (map.containsKey(num - 1)) {
                int preLength = map.get(num - 1).poll();
                //若num -1 的队列空了，在map中删除
                if (map.get(num - 1).isEmpty()) {
                    map.remove(num - 1);
                }
                map.get(num).offer(preLength + 1);
            } else {
                map.get(num).offer(1);
            }
        }
        for (PriorityQueue<Integer> queue : map.values()) {
            if (queue.peek() < 3) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {

    }
}
